package leetcode_300;



/**
 *@author 周杨
 *HIndex_274 一个n长度的数组 有H个数比它大或者等 n-H个数比它小 求这个数
 *describe:用hash可以在O(n)时间内解决  AC 100%  不用排序
 *2018年6月26日 下午2:25:34
 */
public class HIndex_274 {
	public int hIndex(int[] citations) {
		if (citations == null || citations.length < 1) {
            return 0;
        }
        //h-index wouldn't exceed the total number of articles
        //for example, even it is cited[100, 98, 0, 1, 5], we will only care about the number of cites including or below 5
        int n = citations.length; //n: number of articles
        int[] count = new int[n + 1];
        for (int i : citations) {
            if (i < n) {
                count[i]++;
            } else {
                count[n]++;//把大于n的数全存在最后一个坐标中   
            }
        }
        int sum = 0;
        int max = 0;
        for (int i = n; i >= 0; i--) {
            sum += count[i];//总是从最有可能的数开始筛选 sum就是比i大的数的总数量 如果>=i 就是解  因为剩下的数都是满足的
            if (sum >= i) {
                max = i; 
                break;
            }
        }
        return max;
    }
}
